/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/populating-next-right-pointers-in-each-node
   @Language: C++
   @Datetime: 19-08-01 17:55
   */

/*
// Definition for a Node.
class Node {
public:
	int val;
	Node* left;
	Node* right;
	Node* next;

	Node() {}

	Node(int _val, Node* _left, Node* _right, Node* _next) {
		val = _val;
		left = _left;
		right = _right;
		next = _next;
	}
};
*/

// Method 1, level traversal, Time O(n), Space O(h)
class Solution {
public:
	Node* connect(Node* root) {
		if(root==NULL) return NULL;
		queue<Node*> q;
		for(q.push(root); q.size();){
			for(int i=q.size(); i--;){
				Node *pre=q.front();
				q.pop();
				pre->next=i?q.front():NULL;
				if(pre->left) q.push(pre->left);
				if(pre->right) q.push(pre->right);
			}
		}
		return root;
	}
};

// Method 2, loop, Time O(n), Space O(1)
class Solution {
public:
	Node* connect(Node* root) {
		for(Node *pre=root; pre; pre=pre->left){
			for(Node *cur=pre; cur; cur=cur->next){
				if(cur->left) cur->left->next=cur->right;
				if(cur->right && cur->next) cur->right->next=cur->next->left;
			}
		}
		return root;
	}
};
